package _11_整理题目._2_二叉树_递归_dfs_bfs;

import org.junit.Test;
import util.TreeNode;

/**
 * 给定一棵完全二叉树的头节点head，返回这棵树的节点个数。如果完全二叉树的节点数为N，
 * 请实现时间复杂度低于O(N)的解法。 
 * 
 * 方法一：层级遍历，统计节点数，O(N)
 * 方法二：二分递归，根据 满二叉树节点数 = 2^n -1 公式直接计算
 *      递归参数确定，输入 root，返回 总的节点数
 *      递归结束条件，如果 root == 0，return 0
 *      递归判断逻辑
 *          求左子树的深度，和右子树的深度
 *          如果左子树的深度 == 右子树的深度
 *              说明左子树是满二叉树，返回 左子树节点总数2^n-1 + 根节点1 + 递归右子树
 *          如果不等，即左子树高度 = 右子树高度 + 1
 *              说明右子树是满二叉树，返回 右子树节点总数2^n-1 + 根节点1 + 递归左子树
 *      
 *      计算一个完全二叉树的深度，让指针一直往左子树走，==null 时即可统计深度
 *      
 */
public class _09_完全二叉树结点数 {
    
    public int nodeNum(TreeNode head) {
        if(head == null) return 0;
        
        int leftHeight = getHeight(head.left);
        int rightHeight = getHeight(head.right);
        if(leftHeight == rightHeight) {
            return (int)Math.pow(2, leftHeight) + nodeNum(head.right);
        } else {
            return nodeNum(head.left) + (int)Math.pow(2, rightHeight);
        }
    }
    
    private int getHeight(TreeNode root) {
        int deep = 0;
        while(root != null) {
            deep++;
            root = root.left;
        }
        return deep;
    }
    
    @Test
    public void main() {
        Integer[] input = {1, 2, 3, 4, 5};
        TreeNode root = TreeNode.getTreeFromArray(input);
        System.out.println(nodeNum(root));
    }
    
}
